<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>双向链表</title>
  </head>
  <body>
    <script type="text/javascript">
      // 创建双向链表的构造函数
      // 基本思路和单向链表比较相似, 都是创建节点结构函数以及定义一些属性和方法.
      // 只是Node中添加了一个this.prev属性, 该属性用于指向上一个节点.
      // 另外属性中添加了一个this.tail属性, 该属性指向末尾的节点
      function DoublyLinkedList() {
        // 创建节点构造函数
        function Node(data) {
          this.data = data
          this.next = null
          this.prev = null // 新添加的
        }

        // 定义属性
        this.length = 0
        this.head = null
        this.tail = null // 新添加的

        // 定义相关操作方法

        //1.append方法
        DoublyLinkedList.prototype.append = function(data) {
          // 创建节点
          let newNode = new Node(data)
          if (this.head == null) {
            this.head = newNode
            this.tail = newNode
          } else {
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
          }
          this.length += 1
        }

        // 2.toString方法
        DoublyLinkedList.prototype.toString = function() {
          return this.forwardString()
        }

        // 正向遍历的方法
        DoublyLinkedList.prototype.forwardString = function() {
          let current = this.head
          let forwardStr = ""

          while (current) {
            forwardStr += "," + current.data
            current = current.next
          }

          return forwardStr.slice(1)
        }

        // 反向遍历的方法
        DoublyLinkedList.prototype.reverseString = function() {
          let current = this.tail
          let reverseStr = ""

          while (current) {
            reverseStr += "," + current.data
            current = current.prev
          }

          return reverseStr.slice(1)
        }
        
        // 3.insert在任意位置插入数据
        DoublyLinkedList.prototype.insert = function(position, data) {
          // 1.判断越界的问题
          if (position < 0 || position > this.length) return false
          // 2.创建新的节点
          let newNode = new Node(data)
          // 3.判断插入的位置
          if (position === 0) { // 在第一个位置插入数据
            // 判断链表是否为空
            if (this.head == null) {
              this.head = newNode
              this.tail = newNode
            } else {
              this.head.prev = newNode
              newNode.next = this.head
              this.head = newNode
            }
          } else if (position === this.length) { // 插入到最后的情况
            // 思考: 这种情况是否需要判断链表为空的情况呢? 答案是不需要, 为什么?
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
          } else { // 在中间位置插入数据
            // 定义属性
            let index = 0
            let current = this.head
            let previous = null

            // 查找正确的位置
            while (index++ < position) {
              previous = current
              current = current.next
            }

            // 交换节点的指向顺序
            newNode.next = current
            newNode.prev = previous
            current.prev = newNode
            previous.next = newNode
          }

          // 4.length+1
          this.length++
          return true
        }
        
        // 4.get方法获取对应位置的数据
        DoublyLinkedList.prototype.get = function(position) {
          // 1.判断越界的问题
          if (position < 0 || position >= this.length) return null
          // 定义属性
          let index = 0
          let current = this.head
          // 查找正确的位置
          while (index++ < position) {
            current = current.next
          }
          return current.data
        }
        
        //5.indexOf方法根据数据获取索引
        DoublyLinkedList.prototype.indexOf = function(data) {
          // 1.定义变量
          let current = this.head
          let index = 0
          //2.开始查找
          while (current) {
            if (current.data === data) {
              return index
            } else {
              current = current.next
              index += 1
            }
          }
          // 3.未查找到
          return -1
        }
        
        //6.update方法
        DoublyLinkedList.prototype.update = function(position, newdata) {
          // 1.对position进行越界处理
          if (position < 0 || position >= this.length) return false
          // 2.查找正确的节点
          let current = this.head
          let index = 0
          while (index++ < position) {
            current = current.next
          }
          // 修改data
          current.data = newdata
          return true
        }
        
        // 7.removeAt方法根据位置删除对应的元素
        DoublyLinkedList.prototype.removeAt = function(position) {
          // 1.判断越界的问题
          if (position < 0 || position >= this.length) return null

          // 2.判断移除的位置
          // current表示要删除的节点
          let current = this.head
          if (position === 0) {
            if (this.length == 1) {
              this.head = null
              this.tail = null
            } else {
              this.head = this.head.next
              this.head.prev = null
            }
          } else if (position === this.length - 1) {
            current = this.tail
            this.tail = this.tail.prev
            this.tail.next = null
          } else {
            let index = 0
            let previous = null
            while (index++ < position) {
              previous = current
              current = current.next
            }

            previous.next = current.next
            current.next.prev = previous
          }

          // 3.length-1
          this.length--

          return current.data
        }
        
        // 8.remove方法根据位置删除对应的元素
        DoublyLinkedList.prototype.remove = function(data) {
          let index = this.indexOf(data)
          return this.removeAt(index)
        }
        
        //9.isEmpty方法
        DoublyLinkedList.prototype.isEmpty = function() {
          return this.length == 0
        }
        
        //10.size方法
        DoublyLinkedList.prototype.size = function() {
          return this.length
        }
        // 11.getHead方法获取链表第一个元素
        DoublyLinkedList.prototype.getHead = function() {
          return this.head.data
        }
        // 12.gettail方法获取链表最后一个元素
        DoublyLinkedList.prototype.gettail = function() {
          return this.tail.data
        }
      }
      
      
      
      // 1.创建双向链表对象
      let list = new DoublyLinkedList()

      // 2.追加元素
      list.append("abc")
      list.append("cba")
      list.append("nba")
      list.append("mba")
      alert("测试append方法\n" + list)
      // 3.获取所有的遍历结果
      alert("测试toString方法\n" + list.forwardString()) // abc,cba,nba,mba
      alert("测试toString方法\n" + list.reverseString()) // mba,nba,cba,abc
      alert("测试toString方法\n" + list) // abc,cba,nba,mba
      console.log(list)
      // 4.insert方法测试
      list.insert(0, "100")
      list.insert(2, "200")
      list.insert(6, "300")
      alert("测试insert方法\n" + list) // 100,abc,200,cba,nba,mba,300
      console.log(list)
      //5.测试get方法
      alert("测试get方法\n" + list.get(2))
      alert("测试get方法\n" + list.get(0))
      //6.测试indexOf方法
      console.log(list.indexOf("as"))
      console.log(list.indexOf("300"))
      console.log(list.indexOf(200))
      //7.测试update方法
      list.update(0, "12345")
      list.update(1, "1314")
      alert("测试update方法\n" + list) // 12345,1314,200,cba,nba,mba,300
      // 8.removeAt方法测试
      alert("removeAt方法测试\n" + list.removeAt(0)) //12345
      alert("removeAt方法测试\n" + list) // 1314,200,cba,nba,mba,300
      alert("removeAt方法测试\n" + list.removeAt(1)) // 200
      alert("removeAt方法测试\n" + list) // 1314,cba,nba,mba,300
      alert("removeAt方法测试\n" + list.removeAt(4)) // 300
      alert("removeAt方法测试\n" + list) // 1314,cba,nba,mba
      alert("removeAt方法测试\n" + list.removeAt(3)) // mba
      alert("removeAt方法测试\n" + list) // abc,cba,nba
      // 9.remove方法测试
      alert("remove方法测试\n"+list.remove("nba")) // nba
      alert("remove方法测试\n"+list) // abc,cba
      // 10.测试其他方法
      alert("测试其他方法\n"+list)
      alert("测试其他方法\n"+list.isEmpty())
      alert("测试其他方法\n"+list.size())
      alert("测试其他方法\n"+list.getHead())
      alert("测试其他方法\n"+list.gettail())
    </script>
  </body>
</html>
